\documentclass[12pt]{ctexart}
\usepackage{graphicx}
\usepackage{ctex}
\usepackage[a4paper,left=1.25in,right=1.25in,top=1in,bottom=1in]{geometry}

\title{作业二}
\author{刘小川  \\ 学号 3210105317}

\begin{document}
\maketitle

\subsection*{Question 3.1}
\textbf{Probe that one can check the satisfiability of a 2-CNF(a conjunction of disjunctions,each containing two literals) in polynomial time.}
\subsection*{Solution}
对于2-CNF的可满足性，若是直接去寻找合适的x变量可能会非常的繁琐，所以我们利用其一些性质进行化简。首先注意到由两个字母组成的短语$A\vee \neg B $ and $B\vee C$，若是这个连句成立，则意味着$A\vee C$也成立，利用这个性质我们就可以对原式进行改写，这样就可以不断生成新的分离式，当我们不断重复这一过程，知道函数中没有相符合的结构能够继续，这时得到的新合取范式我们记作 
$\tilde{F}$.这时需要注意到，F和$\tilde{F}$这两个bool函数的结果是相同的，这是因为每一步改写时前后bool函数结果都相同。那么通过判断$\tilde{F}$的结果就可以获取F的可满足性了。同时还可以注意到当CNF范式中，若是存在空的析取范式，则$\tilde{F}$就只能为0。那么此种方法可以有多项式内的运行时间`。\par
F的形式为$D_1\wedge D_2\wedge$ ...$\wedge D_m$,$D_1$,$D_2$,...,$D_m$为字符的析取，若是$D_x$中有重复的存在，那么删去之后并不影响公式的结果，所以我们可以把F当作一个析取范式的集合。那么此时更为详细的阐述上面的变换。由于F为2-CNF，则每个析取式中有两个符号，若有$A\vee \neg x$和$C\vee x$同时存在，那么这个2-CNF若想值为1,就必须有$A\vee C$成立，则原来F集合中可以加入一个元素$A\vee C$,这样不断地对有符合上述形式的两个析取范式操作，由于每个析取范式中最多有两个短语，那么得到的新的合取范式也只能为一个两个或者空的短语，这时我们可以证明，如果$\tilde{F}$包含一个空的短语，那么F就不是可满足的。\par
这个定理的证明如下：这里我们用条件更加强的证明，令Y=$l_1\vee \cdots \vee l_k$,我们证明F的结果表示Y当且且仅当$\tilde{F}$中包含短语D能代表Y的成立。这样当Y是空短语时，若$\tilde{F}$也有这样的D是空的，则同样有F的值与空短语相同，为0，此时F就不可能是可满足的。这个定理的充分性很容易证明，因为F属于$\tilde{F}$，所以F能声明$\tilde{F}$中任意短语的成立\par
关于必要性，若是F能声明Y的成立，则若$\tilde{F}$不含有这样的短语D，则F中也不会含有这样的短语D，则不可能有F声明出Y的成立，则矛盾。这样这个定理证明完毕。
对于2-CNF问题，不断应用上面所说的变换方式，可以出现更多的两个以下的析取范式的短语，只要短语中对于同一个后缀$x_j$同时出现$x_j$和$\neg x_j$则由于这是用合取范式连接，那么这个2-CNF问题就不可能是可满足的，因为不管$x_j$为0还是1,其都有一个形式为0造成$\tilde{F}$为0,进而F=$\tilde{F}$=0不可满足。

\subsection*{Question 3.2}
\textbf{Prove that the problem of the existence of an Euler cycle in an undirected graph(an Euler cycle is a cycle that traverses each edge exactly once )belongs to P}
\subsection*{Solution}
首先考虑Euler圈的充要条件，G中若要有Euler圈当且仅当G连通并且G中顶点的度为偶数。关于这个定理的证明，我们只需证明其充分性即可，因为题目中要求我们判断Euler圈的存在性。\par
充分性证明：这里我们通过数学归纳法证明，当k=2，即G中只有两个顶点，若想为Euler图，每个顶点的度数必为偶数。当k=n时我们假设成立，当k=n+1时，我们可以随意删去一个圈，删去之后要求形成两个以上的连通分支，这时每个连通分支其定点个数必小于等于n，那么由归纳假设可知每个连通分支都含有Euler圈，那么在加入原来去掉的圈的边，仍然是加入了偶数个边，原来联通分支就可以合成一个Euler圈，充分性证明完毕。\par
这样有了判断Euler圈存在的充分条件，我们很容易发现，判断这些条件都可以在多项式时间内完成，就比如判断顶点的奇偶性还有连通性的判断。这样就说明了判断Euler圈的存在性问题属于P问题
\subsection*{Question 3.3}
\textbf{Suppose we have an NP-oracle --a magic device that can immediately sove any instance of the SAT problem for us .In other word, for any propositional formula the oracle tells whether it is satisfiable or not. Prove that there is a polynomial-time algorithm that finds a satisfying assignment to a given formula by making a polynomial number of queries to the oracle.(A similar statement is true for the Hamiltonian cycle :fingding a Hamiltonian cycle in a graph is at most polynomially hader than checking for it  existence}
\subsection*{Solution}
这个题目我们要充分利用NP-oracle这个装置，虽然这个装置只是用来判断有没有解，我们可以通过更改问题的设置，来利用NP-oracle，比如我们需要找到$F(x_1,x_2,\cdots  x_n)$这一公式值为1对应的变量，那么我们就可以从第一个变量$x_1$的值来逐个尝试下来，比如我们可以问当$x_1=0$时是否是可满足的。如果是，那就直接递推去问$x_2$的相关值问题即可，如果不是，那$x_1$只能为1,同样可以去问$x_2$值的相关问题。这样一直递退至$x_n$的取值，我们就可以得到一串让公式为1的自变量取值。注意算法每一步使用一次NP-oracle装置，那么使用n步的解决时间就是也是多项式的一个时间，这样证明就完毕了。同样对找Hamiltonian cycle这一工作，同样可以对每一个边询问这种问题，最终找到这样的Hamiltonian cycle。
\end{document}